/*
 **********************************************************
 *
 * Program 	 :	heap.c
 *
 * Write by  :	IBRAHIMLI NIHAT
 *
 * Summary 	 :  Contains useful functions 
 * 					for handling on the heap
 *
 * Date 	 :	Avril 27, 2013
 *
 ***********************************************************
 */

 #include "heap.h" 
 #include "graphe.h"

// To initialize the heap
int initHeap(Heap** heap, int nbMaxVertex) {

	// Must be non usable
	if ((*heap) != NULL) {
		printf("Attention, heap is not null - initHeap\n");
		return HEAP_NON_NULL;
	}

	// Create a new heap
	(*heap) = (Heap *) malloc (sizeof(Heap));

	if ((*heap) == NULL) {
		return PROBLEME_MEMOIRE;
	}

	// Initialize heap
	(*heap)->nbMember = 0;
	(*heap)->size = nbMaxVertex;
	(*heap)->array = NULL;
	(*heap)->array = (TypHeap*) malloc(sizeof(TypHeap) * (*heap)->size);

	if ((*heap)->array == NULL) {
		return PROBLEME_MEMOIRE;
	}

	return RES_OK;
}

//Insert an element of type TypHeap into the heap 
int insertElem(Heap* heap, TypHeap elem) {

	// Create heap if it is null
	if (heap == NULL) {
		printf("Attention - heap was null, created insertElem\n");
		return HEAP_NULL;
	}

	// the number of member must be less than the heap size
	if (heap->nbMember >= heap->size)
	{
		printf("Attention - heap is full, created insertElem\n");
		return HEAP_OVERFLOW;
	}
		
	// Increment heap size
	heap->nbMember++;

	// Add new element into Heap
	heap->array[heap->nbMember - 1] = elem;

	return RES_OK;
}

// give index of left child 
int leftChild(int index){
	return 2 * index;
}

// give index of right child 
int rightChild(int index){
	return 2 * index + 1;
}

// give index of parent
int parent(int index){
	return index / 2;
}

//replace the values of index1 and index2
void swap(Heap* heap, int index1, int index2){
   	TypHeap element;
    element = heap->array[index1];
    heap->array[index1] = heap->array[index2];    
    heap->array[index2] = element;
}

// sort the heap
int heapSort(Heap* heap, int index){    	
	if (heap == NULL)
	{
		printf("Attention - heap is null, heapSort\n");
		return HEAP_NULL;
	}	
	if (heap->nbMember < 1)
	{
		printf("Attention - heap is empty, heapSort\n");
		return HEAP_EMPTY;	
	}
	if (index <= 0)
	{
		return HEAP_INDEX_ERROR;
	}
	if (heap->nbMember <= index)
	{		
		return HEAP_INDEX_ERROR;
	}

    int lChild = leftChild(index);
    int rChild = rightChild(index); 	
    
    index = index - 1;
    lChild = lChild - 1;
    rChild = rChild - 1;
    int min = index;           

    // if the parent is greater than the left child
    if(lChild < heap->nbMember && heap->array[lChild].weight < heap->array[index].weight){
        min = lChild;    
    }    

    // if the min value is greater than the left child
    if(rChild < heap->nbMember && heap->array[rChild].weight < heap->array[min].weight){
    	min = rChild;
	}

    if(min != index){  
    	// exchange the values of index and min
        swap(heap,index,min);        
        // launche heapSort with new min
        heapSort(heap,min+1);
    }

    return RES_OK;
}

// build the heap
int  buildHeap(Heap* heap){
    int i;
    //  luanch heapSort from the middle of the heap
    for(i = (heap->nbMember)/2; i >= 1; i--){    	
        int err = heapSort(heap,i);
        if (err != RES_OK)
        {
        	return err;
        }
    }
    return RES_OK;
}

//extract an element of type TypHeap which its value of weight is min
int extractMin(Heap* heap, TypHeap* elem){	
	if (heap == NULL)
	{
		printf("Attention - heap is null, extractMin\n");
		return HEAP_NULL;
	}	
	if (heap->nbMember < 1)
	{
		printf("Attention - heap is empty, extractMin\n");
		return HEAP_EMPTY;	
	}

	int err = buildHeap(heap);
	
	if (err != RES_OK)
	{
		return err;
	}	

	*elem = heap->array[0];		
	heap->array[0] = heap->array[heap->nbMember - 1];
	heap->nbMember--;

	err = buildHeap(heap);	
	
	if (err != RES_OK)
	{
		return err;
	}	
	return RES_OK;
}

// check out the member of the heap
int memberOfHeap(Heap heap, int vertex){
	int i ;
	for (i = 0; i < heap.nbMember; ++i)
	{
		TypHeap elem = heap.array[i];
		// if the vertex value is equal to the value that is passed as a parameter
		if (elem.vertex == vertex)
		{
			return 1;
		}
	}

	return 0;
}

// give the value of the weight of vertex
double getWeightOfVertex(Heap heap, int vertex ){
	int i ;
	for (i = 0; i < heap.nbMember; ++i)
	{
		TypHeap elem = heap.array[i];
		// if the vertex value is equal to the value that is passed as a parameter
		if (elem.vertex == vertex)
		{
			return elem.weight;
		}
	}
	return HEAP_VERTEX_NOT_FOUND;
}

// set the predecessor of vertex
int setPredecessorVertex(Heap* heap, int vertex, int predecessorVertex){
	int i ;
	for (i = 0; i < heap->nbMember; ++i)
	{
		TypHeap elem;
		elem = heap->array[i];
		// if the vertex value is equal to the value that is passed as a parameter
		if (elem.vertex == vertex)
		{
			elem.predecessorVertex = predecessorVertex;
			heap->array[i] = elem;		
			return RES_OK;
		}
	}

	return HEAP_VERTEX_NOT_FOUND;
}

// set the weight of the vertex 
int setWeightOfVertex(Heap* heap, int vertex, double weight){	
	int i ;
	for (i = 0; i < heap->nbMember; ++i)
	{
		TypHeap elem;
		elem = heap->array[i];
		// if the vertex value is equal to the value that is passed as a parameter
		if (elem.vertex == vertex)
		{
			elem.weight = weight;
			heap->array[i] = elem;
			return RES_OK;
		}
	}

	return HEAP_VERTEX_NOT_FOUND;
}
void printHeap(Heap heap){
	int i;
	printf("\nHeap\n");
	printf("size of Array : %d\n", heap.size);
	printf("number of member : %d\n", heap.nbMember);
	for (i = 0; i <heap.nbMember ; ++i)
	{
		printf("Into : %d case \n", i + 1);
		printf("\tVertex : %d\n", heap.array[i].vertex);
		printf("\tWeight : %f\n", heap.array[i].weight);
		printf("\tPredecessor Vertex : %d\n", heap.array[i].predecessorVertex);
	}	
}

// Free heap from memory
int freeHeap(Heap* heap) {
	if (heap == NULL) {
		printf("Attention - heap was null, created freeHeap\n");
		return HEAP_NULL;
	}
	if (heap->array != NULL) {
		free(heap->array);

		heap->array = NULL;
		heap->nbMember = 0;
	}
	if (heap != NULL) {
		free(heap);
		heap = NULL;
	}
	return RES_OK;
}